

<HTML>

<HEAD>

<LINK rel="stylesheet" href="../exer.css">

</HEAD>

<BODY>

<H1>

Data Structures, Algorithms, & Applications in C++<BR>

Chapter 13, Exercise 17<BR>

<BR>

</H1>





<dl compact>

<dt> (a)

<dd>

The profit densities are [0.2, 1.5, 1.5].  Therefore we consider the objects

in the order 2, 3, 1.  Objects 2 and 3 are packed and then

0.85 of object 2 is packed.

The solution is <code class=code>x</code> = [0.85, 1, 1] and the profit

earned from the packing is 47.



<dt> (b)

<dd>

Consider any instance of the continuous knapsack problem.

We may assume that the objects are given in nonincreasing order of profit

density.  Let <em class=var>x<sub>1</sub> ... x<sub>n</sub></em>

be the greedy solution and let

<em class=var>y<sub>1</sub> ... y<sub>n</sub></em> be an optimal solution.

We shall show that both solutions earn the same profit and so the greedy

solution is also optimal.

<br><br>

Let <em class=var>j</em> be the least integer such that

<em class=var>x<sub>i</sub> = y<sub>i</sub></em>,

<em class=var>1 <= i < j</em> and <em class=var>x<sub>j</sub> != y<sub>j</sub></em>.

If no such <em class=var>j</em> exists, the two solutions are the same and

so the greedy solution is optimal.  Assume such a <em class=var>j</em> exists.

From the way the greedy algorithm works and the fact

that the optimal solution is a feasible solution, we conclude that

<em class=var>x<sub>j</sub> > y<sub>j</sub></em>.

If we increase the fraction of object <em class=var>j</em> in the

optimal solution to <em class=var>x<sub>j</sub></em>

and reduce the fraction of objects <em class=var>j+1, j+2, ...</em>

to compensate for the increased weight used by object <em class=var>j</em>,

the profit cannot decrease because we are replacing lower density

fractions by higher or equal density ones.  This transformation,

therefore, yields a new optimal solution for which

the least integer <em class=var>j</em> such that

<em class=var>x<sub>i</sub> = y<sub>i</sub></em>,

<em class=var>1 <= i < j</em> and <em class=var>x<sub>j</sub> != y<sub>j</sub></em>

(if it exists) is larger than for the old optimal solution.

<br><br>

By repeatedly applying this transformation, we convert the original

optimal solution into the greedy solution without decreasing

the profit earned.  So the greedy solution must also be optimal.



<dt> (c)

<dd>

We shall assume that the profits are of type <code class=code>float</code>

or <code class=code>int</code>.  First we define a class

<code class=code>object</code> which is used to sort the objects into

nondecreasing order of profit density.  Following the sort, the objects are

to be packed into the knapsack in the reverse of this order.

The class

<code class=code>object</code> is given below and in the file

<code class=code>object2.h</code>.



<HR class = coderule>

<pre class = code>

class Object {

   friend float Knapsack(int [], int [], int, int, float []);

   public:

      operator float() const

      {return d;}

   private:

      int ID;  // object identifier

      float d; // profit density

};

<hr class=coderule>

</pre>

<br><br>



The function

<code class=code>Knapsack</code> packs the objects into the knapsack

in nonincreasing order of profit density.  It returns the profit

generated by the greedy packing.  It also sets <code class=code>x[i]</code>

to be the fraction of object <code class=code>i</code> that is packed

into the knapsack.



<HR class = coderule>

<pre class = code>

template&lt;class Tw, class Tp&gt;

float Knapsack(Tp p[], Tw w[], Tw c, int n, float x[])

{// Return value of best knapsack filling. 

 // Set x[i] = fraction of object i included in knapsack,

 // 1 &lt;= i &lt;= n.

   float P = 0;  // will be sum of profits



   // define an object array to be sorted by

   // profit density

   Object *Q = new Object [n+1];



   for (int i = 1; i &lt;= n; i++) {

      // array of profit densities

      Q[i].ID = i;

      Q[i].d = 1.0*p[i]/w[i];

      }





   // sort by density

   HeapSort(Q,n);



   // load in nonincreasing order of density

   int i;

   for (i = n; i &gt; 0; i--) {

      int id = Q[i].ID;

      if (w[id] &lt;= c ) {// object id fits

         x[id] = 1;

         c -= w[id];

         P += p[id];

         }

      else {// object id is too large

         // take a fraction of this object to fill knapsack

         float f = 1.0*c/w[id];

         x[id] = f;

         P += f*p[id];

         break;

         }

      }



   // set remaining x[] values to zero

   for (int j = i-1; j &gt; 0; j--)

      x[Q[j].ID] = 0;



   delete [] Q;

   return P;

}

<HR class = coderule>

</pre>

<br><br>



The above code together with test data and output appear in the files

<code class=code>cknap.*</code>.

<br><br>

Since the knapsack will usually get filled after

the first few items have been examined, we can avoid doing a

total sort as is done above.  Instead, we can start by

setting all <code class=code>x[i]</code> to zero and

initializing a max heap with the objects.  Then objects

are extracted from the max heap one by one and packed into the

knapsack until the knapsack is full.  Sine a max heap can

be initialized in linear time, the complexity of the new knapsack

algorithm is O(<em class=var>n + k log n</em>), where

<em class=var>k</em> is the number of objects extracted

from the max heap.

In the worst case, <em class=var>k = n</em> and the complexity

becomes the same as when we started by sorting the objects.

</dl>



</FONT>

</BODY>

</HTML>

